#include "Sort.h"

void InsertSort(int* arr, int n) {
	if (arr == NULL || n <= 1) {
		return;
	}
	//外层循环每次++将一个待排序值加入排序
	//tmp为下标site+1的值，故n-1
	for (int site = 0; site < n - 1; site++) {
		int cur = site;			//cur记录下标
		int tmp = arr[cur + 1];	//tmp为待排序值

		//内层循环将大于tmp的值往后挪
		while (cur >= 0 && arr[cur] > tmp) {
			arr[cur + 1] = arr[cur];
			cur--;
		}

		//若cur==-1，说明tmp为0~site-1的最小值，故把tmp放到下标0位置
		//若cur>=0，说明tmp比下标cur的值要大，故把tmp放到下标cur+1位置
		arr[cur + 1] = tmp;
	}
}

//另一种插入排序的实现方式
void InsertSort_2(int* arr, int n) {
	for (int cur_1 = 0; cur_1 < n - 1; cur_1++) {
		for (int cur_2 = cur_1 + 1; cur_2 > 0 && arr[cur_2] < arr[cur_2 - 1]; cur_2--) {
			Swap(&arr[cur_2], &arr[cur_2 - 1]);
		}
	}
}